/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
export var exist = function (board, word) {
  const [m, n] = [board.length, board[0].length]
  const dirt = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ]
  const visited = new Array(m).fill(0).map(() => new Array(n).fill(false))
  // 从座标[r][c]开始搜索，word的第k位字符是否与board[r][c]相等
  function dfs(r, c, k = 0) {
    if (board[r][c] !== word[k]) return false
    if (k === word.length - 1) return true
    visited[r][c] = true

    for (const [offsetR, offsetC] of dirt) {
      const [nextR, nextC] = [r + offsetR, c + offsetC]
      if (nextR < 0 || nextR >= m || nextC < 0 || nextC >= n) continue
      if (visited[nextR][nextC]) continue
      const res = dfs(nextR, nextC, k + 1)
      if (res) return true
    }
    visited[r][c] = false
    return false
  }
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (dfs(i, j, 0)) return true
    }
  }
  return false
}
